package com.frx.datastruct.chapterten;

import java.util.TreeMap;

/**
 * Created by xurenfeng on 2019/3/11.
 * 字典树
 */
public class Trie {

    private class Node{
        public boolean isWord;
        public TreeMap<Character,Node> next;

        public Node(boolean isWord){
            this.isWord = isWord;
            next = new TreeMap<>();
        }
        public Node(){
            this(false);
        }
    }

    private Node root;
    private int size;

    public int getSize(){
        return size;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    /** 字典树的添加*/
    public void add(String word){

        Node cur = root;
        for (int i = 0; i < word.length();i++){
            char c = word.charAt(i);
            if (cur.next.get(c) == null){
                cur.next.put(c,new Node());
            }
            cur = cur.next.get(c);
        }
        if (!cur.isWord){
            cur.isWord = true;
            size ++;
        }
    }
    /** 查询是否包含某个单词*/
    public boolean contains(String word){
        Node cur = root;
        for (int i = 0; i<word.length();i++){
            char c = word.charAt(i);
            if (cur.next.get(c) == null){
                return false;
            }
            cur = cur.next.get(c);
        }
        return cur.isWord;
    }

    /** 前缀查询*/
    public boolean isPrefix(String prefix){
        Node cur = root;
        for (int i = 0;i<prefix.length();i++){
            char c = prefix.charAt(i);
            if (cur.next.get(c) == null){
                return false;
            }
            cur = cur.next.get(c);
        }
        return true;
    }
    /** 模糊查询  .能匹配所有的单词 */
    public boolean match(String word){
        return match(word,root,0);
    }

    private boolean match(String word,Node node,int index){
        if (index == word.length()){
            return true;
        }
        char c = word.charAt(index);
        if (c != '.'){

        } else {

        }
        return false;
    }
}
